#ifndef BINARYSEARCHTREE_H
#define BINARYSEARCHTREE_H

namespace sk {

template<class T> class BinarySearchTree;

template <class T>
class Node {
public:
    Node(const T& value);

    T value();

    void setLeft(Node<T>* left);
    void setRight(Node<T>* right);

    friend class BinarySearchTree<T>;
private:
    T pValue;
    Node<T>* pLeft;
    Node<T>* pRight;

    int compareTo(const Node<T>& other) const;
    int compareTo(const T& value) const;
};

template <class T>
class Node<T*> {
public:
    Node(T* value);

    void setLeft(Node<T>* left);
    void setRight(Node<T>* right);

    template <class Y> friend class BinarySearchTree;
private:
    T* pValue;
    Node<T>* pLeft;
    Node<T>* pRight;

    int compareTo(const Node<T>& other) const;
    int compareTo(const T* const value) const;
};

class AbstractSearchTree {
public:
    enum DepthFirstSearchType {
        DFST_PREORDER, DFST_INORDER, DFST_POSTORDER
    };
};


template <class T>
class BinarySearchTree : public AbstractSearchTree
{
public:
    BinarySearchTree() : pnRoot(NULL) {}

    Node<T>* find(const T& value) const;
    Node<T>* insert(const T& value);

    typedef void VisitFunc(Node<T>* const, int);

    int depth();
    int size();

    void breadthFirst(VisitFunc visit);
    void depthFirstSearch(VisitFunc visit, DepthFirstSearchType type);
private:
    Node<T>* pnRoot;

    Node<T>* _find(const Node<T>* const node, const T& value) const;
    Node<T>* _insert(Node<T>* const node, const T& value);

    void _breadthFirst(Node<T>* const node, VisitFunc visit);
    void _depthFirstSearch(Node<T>* const node, VisitFunc visit, DepthFirstSearchType type);

    void _depth(Node<T>* const node, int current, int& result);
    void _size(Node<T>* const node, int& result);
};

/*
template <class T>
class BinarySearchTree<T*>
{
public:
    BinarySearchTree();

    Node<T*>* find(const T* value) const;
    Node<T*>* insert(const T* value);
private:
    Node<T*>* pnRoot;

    Node<T*>* _find(const Node<T*>* const node, const T* value) const;
    Node<T*>* _insert(Node<T*>* const node, const T* value);

    void breadthFirst(Node<T*>* const node, void(*visit)(Node<T*>* const));
};
*/

}

#include "binarysearchtree.hpp"

#endif // BINARYSEARCHTREE_H
